package com.soul.sort;

import java.util.Arrays;

/**
 * 基数排序
 */
public class BasedSort {

    public static void sort(int[] a){
        int max = bsort(a, 1);
        for (int i = 1; i <= max; i++) {
            bsort(a, (int) Math.pow(10,i));
        }
    }

    /**
     * 基数：取各位的值，放置于一个既定的槽中（即0-9十个数字）
     * 将数字按照一定的基数进行拆分为多个链表
     * 多次执行之后，将链表中的数字组合起来就是一个有序的数组
     */
    private static int bsort(int[] a,int c){
        Based[] base = new Based[10];
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            int d = a[i] / c % 10;
            max = (a[i]+"").length() > max ? (a[i]+"").length() : max;
            if (base[d] == null)
                base[d] = new Based(a[i]);
            else
                base[d].insert(new Based(a[i]));
        }
        int x = 0;
        int i = 0;
        while (x < base.length) {
            Based b = base[x];
            while (i < a.length){
                if (b == null){
                    break;
                }
                a[i] = (int) b.obj;
                b = b.next;
                i ++;
            }
            x++;
        }
        return max;
    }

    /**
     * 基数类
     */
    private static class Based{
        private Object obj;
        private Based next;

        public Based(Object obj) {
            this.obj = obj;
        }

        public void insert(Based based){
            if (this.next == null){
                this.next = based;
            }else {
                Based t = this;
                while (t.next != null){
                    t = t.next;
                }
                t.next = based;
            }
        }

        public Object getObj() {
            return obj;
        }

        public void setObj(Object obj) {
            this.obj = obj;
        }

        public Based getNext() {
            return next;
        }

        public void setNext(Based next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return "Based{" +
                    "obj=" + obj +
                    ", next=" + next +
                    '}';
        }
    }
}
